package leetcode_801_900;

import java.util.*;

public class LeeCode_815_2 {
    public static void main(String[] args) {
        System.out.println(numBusesToDestination(new int[][]{{1, 2, 7}, {3, 6, 7}}, 1, 6));
        System.out.println(numBusesToDestination(new int[][]{{1, 2, 7}, {3, 6, 7}, {4, 5, 6}}, 3, 7));
        System.out.println(numBusesToDestination(new int[][]{{1, 2}, {2}}, 1, 2));
        System.out.println(numBusesToDestination(new int[][]{{1, 2, 3}, {2,3,5}, {3,4,5}, {4, 5, 6}}, 1, 6));
        System.out.println(numBusesToDestination(new int[][]{{1, 7}, {3, 5}}, 5, 3));
    }
    private static int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target)
            return 0;
        int n = routes.length;
        boolean[][] edge = new boolean[n][n];
        Map<Integer, List<Integer>> rec = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int site : routes[i]) {
                List<Integer> list = rec.getOrDefault(site, new ArrayList<>());
                for (Integer j : list) {
                    edge[i][j] = edge[j][i] = true;
                }
                list.add(i);
                rec.put(site, list);
            }
        }
        int[] dis = new int[n];
        Arrays.fill(dis, -1);
        Queue<Integer> que = new LinkedList<>();
        for (Integer bus : rec.getOrDefault(source, new ArrayList<>())) {
            dis[bus] = 1;
            que.offer(bus);
        }
        while (!que.isEmpty()){
            Integer i = que.poll();
            for (int j = 0; j < n; j++) {
                if (edge[i][j] && dis[j] == -1){
                    dis[j] = dis[i] + 1;
                    que.offer(j);
                }
            }
        }
        List<Integer> list = rec.getOrDefault(target, new ArrayList<>());
        int ans = Integer.MAX_VALUE;
        for (Integer i : list) {
            if (dis[i] > 0){
                ans = Math.min(dis[i], ans);
            }
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

}